home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 247_02 / mersenne.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-04-17  |  896 b   |  40 lines
  1. /*
  2.  *   Program to calculate mersenne primes
  3.  *   using Lucas-Lehmer test - Knuth p.391
  4.  */
  5.  
  6. #include <stdio.h>
  7. #include "miracl.h"
  8. #define LIMIT 128 
  9.  
  10. main()
  11. { /* calculate mersenne primes */
  12.     big L,m;
  13.     int i,k,q;
  14.     int *primes;
  15.     mirsys(100,MAXBASE);
  16.     L=mirvar(0);
  17.     m=mirvar(0);
  18.     primes=gprime(LIMIT);
  19.     for (k=1;;k++)
  20.     { /* test only prime exponents */
  21.         q=primes[k];
  22.         if (q==0) break;
  23.         expb2(m,q);
  24.         decr(m,1,m);
  25.         convert(4,L);
  26.         for(i=1;i<=q-2;i++)
  27.         { /* Lucas-Lehmer test */
  28.             multiply(L,L,L);
  29.             decr(L,2,L);
  30.             divide(L,m,m);
  31.         }
  32.         if (size(L)==0)
  33.         { /* mersenne prime found! */
  34.             printf("2^%d-1 is prime = \n",q);
  35.             cotnum(m,stdout);
  36.         }
  37.     }
  38. }
  39.  
  40.